Metode Nelder-Mead

'

Artikel ini bukan mengenai Metode simpleks untuk penyelesaian masalah optimisasi linear.

Metode Nelder-Mead diterapkan untuk mencari nilai minimum fungsi Himmelblau.

Metode Nelder-Mead, dikenal pula sebagai metode polihedron fleksibel, metode amoeba, atau metode downhill simplex, adalah suatu metode numerik untuk menemukan nilai minimum atau maksimum dari sebuah fungsi objektif multivariabel. Metode ini termasuk metode telusur langsung (dengan membandingkan nilai fungsi) dan umum diterapkan pada masalah optimisasi nonlinear dengan turunan fungsi objektif yang mungkin tidak diketahui. Akan tetapi, metode Nelder-Mead juga merupakan metode telusur heuristik, yang dapat konvergen ke titik non-stasioner pada masalah yang bisa diselesaikan oleh metode-metode alternatif.

Metode Nelder-Mead diperkenalkan oleh John Nelder dan Roger Mead pada tahun 1965, sebagai pengembangan metode Spendley et al. Sebagai contoh penerapan, metode ini dapat dipakai untuk menghitung komposisi beton bertulang pada struktur beton bertulang, sehingga dapat diketahui komposisi struktur yang efisien apabila diketahui harga masing-masing komponen struktur beton bertulang.

Gambaran umum

Metode Nelder-Mead menggunakan konsep simpleks, yakni suatu bentuk politop yang memiliki $n+1$ sisi dalam $n$ dimensi. Contoh-contoh simpleks antara lain adalah: ruas garis dalam ruang satu dimensi, segitiga dalam ruang dua dimensi, tetrahedron dalam ruang tiga dimensi, dan seterusnya. Metode ini menentukan hampiran nilai optimal dari masalah dengan $n$ variabel, yang fungsi objektifnya bersifat mulus dan unimodal. Penerapan metode yang umum adalan untuk mencari minimum fungsi; mencari maksimum fungsi $f(\mathbf {x} )$ dilakukan dengan meminimumkan $-f(\mathbf {x} )$.

Sebagai contoh, seorang insinyur jembatan gantung harus menentukan tebal setiap penyangga, kabel, dan tiang dari jembatan. Semua komponen tersebut saling bergantung, namun tidak mudah untuk memvisualisasikan dampak dari mengubah tebal dari suatu komponen. Simulasi struktur yang rumit seperti itu sering kali sangat mahal secara komputasi untuk dijalankan, mungkin membutuhkan waktu berjam-jam untuk setiap eksekusi. Metode Nelder-Mead membutuhkan, dalam varian aslinya, tidak lebih dari dua evaluasi per iterasi, kecuali untuk operasi penyusutan yang akan dijelaskan nanti. Hal tersebut yang membuat metode ini menarik, dibandingkan dengan beberapa metode optimasi penelusuran langsung lainnya. Tapi, metode ini mungkin memerlukan total iterasi yang besar untuk mencapai nilai optimal.

Titik-titik pada iterasi metode Nelder-Mead pada ruang dimensi dua.

Pencarian nilai minimum fungsi Simionescu menggunakan Nelder–Mead.

Nelder-Mead dalam $n$ dimensi mencatat sebuah himpunan $n+1$ titik uji yang disusun sebagai sebuah simpleks. Metode ini lalu mengekstrapolasi perilaku fungsi objektif yang diukur pada setiap titik uji untuk menemukan titik uji baru, yang selanjutnya digunakan untuk menggantikan satu titik uji yang lama; lalu proses diulangi lagi. Cara penerapan termudah adalah mengganti titik uji terburuk dengan titik uji yang dihasilkan dari pencerminannya dengan sentroid (titik pusat) dari $n$ titik uji yang lain. Jika titik baru ini lebih baik daripada titik uji terbaik saat ini, kita dapat mencoba merenggangkan titik uji ini dari sentroid. Tapi jika titik baru tidak lebih baik daripada sebelumnya, kita akan mengecilkan ukuran simpleks. Berikut penjelasan yang intuitif dari Numerical Recipes:

Metode downhill simplex sekarang mengambil serangkaian langah, sebagian besar langkah hanyalah menggerakkan titik pada simpleks dengan nilai fungsi terbesar (titik tertinggi) melewati sisi simpleks yang menghadapnya, ke titik yang lebih rendah. Tahap ini disebut pencerminan, dan dilakukan dengan cara yang menjaga volume dari simpleks (untuk mempertahankan sifat non-degeneratifnya). Jika tahap tersebut bisa dilakukan, Metode akan memperbesar simpleks ke suatu arah tertentu untuk mengambil "langkah yang lebih besar". Ketika mencapai "dasar lembah", Metode akan menyempitkan ukuran dirinya dan mencoba mengalir menelurusi lembah. Jika ada situasi ketika metode mencoba "melewati lubang jarum", simpleks akan menyusut dari semua arah, menarik dirinya sendiri disekitar titik terendahnya (terbaik).

Berbeda dengan metode-metode optimisasi modern, heuristik yang digunakan Nelder-Mead dapat konvergen ke titik non-stasioner, kecuali jika masalah memenuhi kondisi-kondisi kuat yang lebih banyak daripada yang diperlukan metode-metode modern. Perbaikan-perbaikan modern untuk heuristik Nelder-Mead telah ditemukan sejak tahun 1979.

Banyak variasi metode yang muncul bergantung dari sifat dari masalah yang ingin diselesaikan. Salah satu variasi yang umum menggunakan simpleks kecil berukuran tetap, yang bergerak mengikuti arah gradien (mirip metode penurunan gradien). Hal ini dapat dibayangkan sebagai sebuah segitiga mengelinding menuruni lembah menuju dasarnya. Metode ini juga dikenal dengan metode polihedron fleksibel. Tapi performa metode ini cenderung buruk ketimbang metode yang dijelaskan pada artikel ini, karena melakukan langkah-langkah kecil yang tidak diperlukan, pada daerah fungsi yang tidak diminati.

Salah satu variasi metode Nelder-Mead

Variasi yang disajikan di bagian ini mirip dengan prosedur yang disajikan pada artikel asli Nelder-Mead. Dalam metode ini, kita ingin meminimumkan fungsi $f(\mathbf {x} )$, dengan $\mathbf {x} \in \mathbb {R} ^{n}$. Titik-titik uji saat ini adalah $\mathbf {x} _{1},\ldots ,\mathbf {x} _{n+1}$.

1. Pengurutan dilakukan berdasarkan nilai dari setiap titik uji, $f(\mathbf {x} _{1})\leq f(\mathbf {x} _{2})\leq \cdots \leq f(\mathbf {x} _{n+1}).$Titik $\mathbf {x} _{n+1}$ akan menjadi titik dengan nilai fungsi terburuk. Cek jika metode perlu dihentikan. Lihat bagian Kriteria penghentian (juga disebut dengan "kekonvergenan").
2. Hitung $\mathbf {x} _{o}$, sentroid dari semua titik uji selain $\mathbf {x} _{n+1}$.
3. Pencerminan Hitung titik hasil pencerminan $\mathbf {x} _{r}=\mathbf {x} _{o}+\alpha (\mathbf {x} _{o}-\mathbf {x} _{n+1})$ dengan $\alpha >0$. Jika titik pencerminan lebih baik daripada titik kedua terburuk namun tidak daripada titik terbaik, dengan kata lain $f(\mathbf {x} _{1})\leq f(\mathbf {x} _{r})<f(\mathbf {x} _{n})$, maka buat simpleks baru dengan menukar titik terburuk $\mathbf {x} _{n+1}$ dengan titik pencerminan $\mathbf {x} _{r}$, dan kembali ke Tahap 1.
4. Perluasan terjadi jika titik pencerminan lebih baik daripada titik terbaik saat ini, $f(\mathbf {x} _{r})<f(\mathbf {x} _{1})$. Hal ini dilakukan dengan menghitung titik perluasan $\mathbf {x} _{e}=\mathbf {x} _{o}+\gamma (\mathbf {x} _{r}-\mathbf {x} _{o})$ dengan $\gamma >1$. Jika titik perluasan lebih baik daripada titik pencerminan, $f(\mathbf {x} _{e})<f(\mathbf {x} _{r})$, maka buat simpleks baru dengan menukar titik terburuk $\mathbf {x} _{n+1}$ dengan titik perluasan $\mathbf {x} _{e}$. Tapi jika tidak, simpleks baru dibuat dengan menukar titik terburuk dengan titik pencerminan $\mathbf {x} _{r}$, dan kembali ke Tahap 1.
5. Penyempitan. Pada tahap ini jelas titik pencerminan lebih buruk daripada titik kedua terburuk, $f(\mathbf {x} _{r})\geq f(\mathbf {x} _{n})$. Selanjutnya:
   • Jika $f(\mathbf {x} _{r})<f(\mathbf {x} _{n+1})$, maka hitung titik penyempitan $\mathbf {x} _{c}=\mathbf {x} _{o}+\rho (\mathbf {x} _{r}-\mathbf {x} _{o})$ dengan $0<\rho \leq 0.5$. Lalu, jika titik penyempitan lebih baik daripada titik pencerminan, $f(\mathbf {x} _{c})<f(\mathbf {x} _{r})$, buat simpleks baru dengan menukar titik terburuk $\mathbf {x} _{n+1}$ dengan titik penyempitan $\mathbf {x} _{c}$, dan kembali ke Tahap 1.
   • Tapi jika tidak, yakni $f(\mathbf {x} _{r})\geq f(\mathbf {x} _{n+1})$, titik penyempitan dihitung sebagai $\mathbf {x} _{c}=\mathbf {x} _{o}+\rho (\mathbf {x} _{n+1}-\mathbf {x} _{o})$ dengan $0<\rho \leq 0.5$. Lalu, jika titik penyempitan lebih baik daripada titik terburuk $f(\mathbf {x} _{c})<f(\mathbf {x} _{n+1})$, buat simpleks baru dengan menukar titik terburuk $\mathbf {x} _{n+1}$ dengan titik penyempitan $\mathbf {x} _{c}$, dan kembali ke Tahap 1.
6. Penyusutan. Tukar nilai setiap titik uji selain titik terbaik ($\mathbf {x} _{1}$) dengan $\mathbf {x} _{i}=\mathbf {x} _{1}+\sigma (\mathbf {x} _{i}-\mathbf {x} _{1})$, lalu kembali ke Tahap 1.

Pada prosedur metode di atas, simbol $\alpha$, $\gamma$, $\rho$ dan $\sigma$ secara berurutan menyatakan koefisien besar pencerminan, perluasan, penyempitan, dan penyusutan. Nilai yang umum digunakan adalah $\alpha =1$, $\gamma =2$, $\rho =1/2$ dan $\sigma =1/2$.

Beberapa tahap dapat dijelaskan secara intuitif sebagai berikut. Dalam tahap pencerminan, $\mathbf {x} _{n+1}$ merupakan titik uji dengan nilai terbesar dibandingkan titik-titik uji lainnya. Kita dapat mengharapkan titik uji yang lebih baik (nilai fungsi yang lebih kecil) dengan mencerminkan titik ini ke sisi simpleks (dengan sentroid $\mathbf {x} _{o}$) yang menghadap dirinya. Lalu pada tahap perluasan, jika titik $\mathbf {x} _{r}$ menjadi minimum terbaik saat ini, kita dapat mengharapkan ada nilai yang lebih baik diantara titik $\mathbf {x} _{o}$ dan $\mathbf {x} _{r}$. Di tahap penyempitan, jika $f(\mathbf {x} _{r})>f(\mathbf {x} _{n})$, kita dapat mengharapkan nilai yang lebih baik di dalam simpleks saat ini. Terakhir, tahap penyusutan mengurus kasus langka ketika titik penyempitan menghasilkan nilai fungsi yang lebih besar, yang menurut kutipan Nelder-Mead dijelaskan berikut:

Proses penyempitan yang gagal jarang ditemui, namun dapat terjadi ketika pada lembah melengkung dan satu titik simpleks terletak sangat jauh dari dasar lembah daripada yang lain; penyempitan dapat menyebabkan titik pencerminan menjauhi dasar lembah dan bukannya menuju ke sana. Alhasil penyempitan-penyempitan berikutnya menjadi tidak berguna. Tindakan yang diusulkan akan menyusutkan simpleks ke arah titik uji terendah, yang pada akhirnya akan membawa semua titik ke dasar lembah.

Akan tetapi, Nash menunjukkan implementasi pada aritmetika presisi-tetap dapat gagal untuk menyusutkan simpleks, sehingga sebuah uji tambahan untuk mengecek ukuran simpleks diperlukan.

Penentuan simpleks awal

Hasil dari metode Nelder-Mead bergantung pada simpleks awal yang dipilih. Simpleks dengan ukuran yang kecil dapat membuat metode sering terjebak dalam penelurusan lokal, dan tidak menghasilkan minimum global. Nelder dan Mead menyarankan simpleks dibuat dari suatu titik $\mathbf {x} _{1},$ dan titik pada setiap dimensi lainnya berjarak konstan dari $\mathbf {x} _{1}.$ Alhasil cara ini sensitif terhadap penskalaan dari variabel-variabel yang menyusun $\mathbf {x}$.

Kriteria penghentian

Suatu kriteria diperlukan untuk menghentikan siklus iterasi. Nelder dan Mead menggunakan nilai standar deviasi sampel dari nilai-nilai fungsi dari simpleks terbaru. Jika nilai tersebut berada dibawah suatu batas toleransi, maka siklus dihentikan dan nilai fungsi terkecil dari simpleks dipilih sebagai nilai optimal. Kriteria ini dapat sensitif terhadap toleransi, khususnya pada fungsi yang "datar", nilai setiap titik uji dapat sangat mirip walau simpleks masih berukuran besar. Nash mengusulkan uji penyusutan sebagai alternatif kriteria penghentian.

Bacaan lebih lanjut

• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 978-0-486-43227-4. 
• Coope, I. D.; Price, C. J. (2002). "Positive Bases in Numerical Optimization". Computational Optimization and Applications. 21 (2): 169–176. doi:10.1023/A:1013760716801. 
• Gill, Philip E.; Murray, Walter; Wright, Margaret H. (1981). "Methods for Multivariate Non-Smooth Functions". Practical Optimization. New York: Academic Press. hlm. 93–96. ISBN 978-0-12-283950-4. 
• Kowalik, J.; Osborne, M. R. (1968). Methods for Unconstrained Optimization Problems. New York: Elsevier. hlm. 24–27. ISBN 0-444-00041-0. 
• Swann, W. H. (1972). "Direct Search Methods". Dalam Murray, W. Numerical Methods for Unconstrained Optimization. New York: Academic Press. hlm. 13–28. ISBN 978-0-12-512250-4. 

Pranala luar

• Nelder–Mead (Downhill Simplex) explanation and visualization with the Rosenbrock banana function
• John Burkardt: Nelder–Mead code in Matlab - Variasi dari metode Nelder–Mead yang digunakan fungsi Matlab fminsearch.
• Nelder-Mead optimization in Python in the SciPy library.
• nelder-mead - Implementasi bahasa Python metode Nelder–Mead
• NelderMead() - Implementasi bahasa Go/Golang
• SOVA 1.0 (freeware) - Simplex Optimization for Various Application